// Created by WXX on 2021/10/14 15:15
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：4 ms, 在所有 C++ 提交中击败了75.59%的用户
 * 内存消耗：6.8 MB, 在所有 C++ 提交中击败了84.65%的用户
 */
class Solution {
public:

    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) return "";
        return str1.substr(0, gcd(str1.size(), str2.size()));
    }

    int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
};

int main() {

    cout << Solution().gcdOfStrings("ABCABC", "ABC") << endl;

    return 0;
}
